'lintcode 最近公共祖先'

Posted on | In

描述

给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。

最近公共祖先是两个节点的公共的祖先节点且具有最大深度。

样例

样例 1:
输入: 给定如下的一棵树，只有一个节点:
1

LCA(1,1) = 1

样例 2:
输入: 给如下的一颗树

  4
 / \
3   7
   / \
  5   6

LCA(3, 5) = `4`

LCA(5, 6) = `7`

LCA(6, 7) = `7`

思路

递归求解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


class Solution {
public:
    /*
     * @param root: The root of the binary search tree.
     * @param A: A TreeNode in a Binary.
     * @param B: A TreeNode in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * A, TreeNode * B) {
        // write your code here
        if (!root || root == A || root == B)
            return root;
        TreeNode *left = lowestCommonAncestor(root->left, A , B);
        TreeNode *right = lowestCommonAncestor(root->right, A, B);
        return left && right ? root: left? left:right;

    }
};
-------------end of filethanks for reading-------------